package problem239;

//239.滑动窗口最大值
//https://leetcode.cn/problems/sliding-window-maximum/?envType=study-plan-v2&envId=top-100-liked

//单调队列

import java.util.ArrayDeque;
import java.util.Deque;

class Solution1 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new ArrayDeque<>();
        for(int i = 0; i < k; i++) {
            while(!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.addLast(i);
        }
        int[] ret = new int[n - k + 1];
        int index = 0;
        ret[index++] = nums[deque.peekFirst()];
        for(int i = k; i<n; i++) {
            while(!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.addLast(i);
            while(deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ret[index++] = nums[deque.peekFirst()];
        }
        return ret;
    }
}